package leetcode.level3;

import static utils.Tool.pt;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 862. 和至少为 K 的最短子数组
 * 参考 官方题解 实现。
 * @author ben
 * @date 2021-10-27 23:49:02 CST
 */
/*
 * 执行用时：34 ms, 在所有 Java 提交中击败了68.29%的用户
 * 内存消耗：48.6 MB, 在所有 Java 提交中击败了76.98%的用户
 */
public class Solution862V2 {

	public static void main(String[] args) {
		SolutionV2 s = new SolutionV2();
		int k = 0;
		
		int[] nums1 = {1};
		k = 1;
		pt("nums1 s.shortestSubarray=" + s.shortestSubarray(nums1, k));
		
		pt();
		
		int[] nums2 = {1,2};
		k = 4;
		pt("nums2 s.shortestSubarray=" + s.shortestSubarray(nums2, k));
		
		pt();
		
		int[] nums3 = {2,-1,2};
		k = 3;
		pt("nums3 s.shortestSubarray=" + s.shortestSubarray(nums3, k));
		
		pt();
		
//		int[] nums4 = {749,658,772,-486,467,760,608,-377,762,-197,290,-432,916,581,-192,426,-248,-500,927,-185,764,885,74,-202,686,618,209,350,-397,-8,608,-81,106,703,653,779,85,-58,619,915,866,568,752,775,682,308,975,73,219,637,-298,-465,632,-491,705,379,980,795,-281,974,5,33,-225,250,345,588,485,658,679,-442,999,655,526,295,-53,213,542,50,554,276,-274,822,-274,-490,-136,-129,12,743,-209,939,651,124,265,993,746,962,291,747,760,-315,-350,512,-458,294,32,327,-456,806,-194,238,-190,521,136,227,804,837,-271,196,693,54,875,-323,-57,-212,725,-35,690,-278,406,789,-352,127,706,6,697,-228,980,965,-63,271,333,394,-34,-416,618,-499,745,-259,589,886,-2,617,345,-315,807,-172,774,135,790,367,-283,-342,-355,95,-247,-327,434,762,364,-140,510,825,-256,-222,473,-495,171,754,-184,569,845,541,-129,-392,67,606,-397,-472,75,556,703,493,601,177,-227,802,-295,2,711,916,-62,56,785,131,848,950,572,-65,741,427,-195,696,685,656,554,-478,886,637,165,560,276,653,-442,302,770,266,163,493,500,-46,473,697,497,50,-483,501,829,943,-190,216,519,751,499,-352,625,838,199,681,-284,800,350,789,517,878,-421,-272,327,410,778,-329,-354,731,473,-81,698,983,677,331,461,941,958,540,840,808,-466,521,-431,-500,63,813,-267,56,-271,654,706,-461,-341,-464,-292,-56,412,598,-353,281,337,99,-38,496,-113,635,109,851,471,-83,-490,927,234,547,482,-186,365,-167,-276,21,453,105,-350,242,373,55,633,179,631,966,-224,695,931,-179,370,742,130,-106,-448,693,-270,-500,-313,867,-29,803,-139,55,615,270,258,13,-283,98,37,41,532,160,-36,453,725,190,684,480,308,640,-93,797,431,-389,-431,931,-113,824,498,-115,-257,-446,556,-448,762,539,-22,151,-160,538,530,-166,-187,-367,794,845,648,451,966,-55,571,-15,722,-471,-466,-198,977,778,347,870,337,15,801,-156,153,6,454,420,408,357,322,300,62,249,420,788,-402,-211,380,980,-442,-27,702,-467,-15,-382,243,804,725,601,872,867,-189,258,-262,133,-387,-407,759,-168,-416,621,620,235,565,-480,950,368,698,-7,-461,389,582,-417,508,913,599,386,781,955,-449,55,-435,359,752,306,965,82,-304,-79,707,-90,841,760,958,517,446,-134,598,-462,633,0,776,-319,971,-5,733,601,101,-492,-310,-199,-454,483,-288,-209,-253,-171,938,437,458,-316,762,198,153,-242,32,982,-41,631,716,-365,638,-147,779,-227,455,-195,-296,180,-217,38,-329,715,-24,772,323,894,743,944,-15,198,-386,246,117,687,378,-161,823,-299,23,96,640,769,54,988,836,861,-305,-28,142,754,857,332,494,337,532,553,287,-188,-291,-252,216,-239,705,-106,-303,-436,538,-82,830,331,-227,437,-291,502,923,92,-66,513,142,204,173,-496,-199,911,562,-322,-278,763,889,249,-17,507,194,854,492,445,-343,-305,1000,494,829,-294,592,375,863,60,879,511,-24,-244,9,262,-456,813,833,-207,-150,162,143,330,971,909,905,147,508,914,8,-298,-175,-324,-453,-297,72,-246,-401,846,375,173,382,-329,981,-101,444,401,986,-475,-240,585,-474,-307,541,-452,929,247,-362,703,934,841,689,913,486,223,776,686,81,72,689,206,178,692,650,986,612,691,-83,568,371,333,-238,-70,878,804,-143,127,990,-395,-244,-308,258,-134,333,-410,184,596,618,-171,905,350,-274,-314,955,777,95,-310,736,-204,151,-173,562,189,-342,700,80,-277,-106,138,585,-25,825,-467,-134,304,-370,-32,-269,173,-422,89,-19,-215,-387,-234,-412,-161,835,834,52,-494,601,157,-157,161,-278,734,309,731,-38,132,154,754,36,179,249,718,582,201,936,626,-233,-191,775,23,-448,925,458,-322,-401,-60,753,-325,297,-354,947,-220,-114,483,86,605,198,337,778,470,85,347,-176,165,205,-258,128,105,-346,-186,752,161,125,972,-330,-453,-193,478,-363,898,-290,-483,69,-383,874,111,-372,399,-438,409,548,-130,-472,179,584,227,39,153,156,-391,687,-213,853,554,132,-295,241,770,-374,755,560,-246,366,235,340,70,612,-393,681,-168,111,283,-443,-452,905,57,728,653,-7,-469,536,206,32,-293,938,-261,636,-20,227,251,-273,577,-465,604,790,589,-237,233,187,447,338,230,-206,631,442,936,-50,496,-246,447,-153,917,24,815,830,406,884,877,232,451,276,-155,50,990,387,206,-118,-264,187,72,204,921,-265,-489,171,914,797,971,887,227,791,671,645,115,-307,901,47,685,-312,-244,-67,-89,864,411,131,342,156,-121,-343,-66,522,-381,534,703,562,886,81,244,-57,-416,535,-366,-55,26,756,500,634,153,-284,916,-171,-490,561,-430,-368,-178,-211,385,362,511,707,658,738,-499,139,45,-50,-262,783,361,279,-110,-122,343,-456,-267,317,19,518,-41,503,363,708,465,778,-448,-285,508,208,99,-414,705,840,-389,660,-453};
//		k = 158015;
//		long t1 =System.currentTimeMillis();
//		result = s.shortestSubarray(nums4, k);
//		long t2 =System.currentTimeMillis();
//		pt("nums4 s.shortestSubarray=" + result + ", time=" + (t2-t1) + "ms");
		
//		// 25813
//		bugFixed(s, "src/main/resources/leetcode862-nums5", 663610288);
//		
//		// 22741
//		bugFixed(s, "src/main/resources/leetcode862-nums6", 5837033);
//		
//		// 19678
//		bugFixed(s, "src/main/resources/leetcode862-nums7", 5006414);
//		
//		// 42622
//		bugFixed(s, "src/main/resources/leetcode862-nums8", 10723661);

	}
	
	private static void bugFixed(final SolutionV2 s, final String fileName, final int k) {
		// 超出时间限制
		int[] nums = initNums(fileName);
		long t1 = System.currentTimeMillis();
		int result = s.shortestSubarray(nums, k);
		long t2 = System.currentTimeMillis();
		pt("bugFixed s.shortestSubarray=" + result);
		pt("t2-t1=" + (t2 -t1));
	}
	
	/**
	 * 读取文件，获取数组 num5：50_000 数据，代码放不下
	 * @author ben
	 * @date 2021-10-27 16:31:54 CST
	 * @param filename 整数，逗号隔开，无空格
	 * @return
	 */
	private static int[] initNums(String filename) {
		int[] ret = null;
		
		File f = new File(filename);
		try (FileInputStream fis = new FileInputStream(f);) {
			
			InputStreamReader isr = new InputStreamReader(fis);
			BufferedReader br = new BufferedReader(isr);
			String line = br.readLine();
			
//			pt("line.length=" + line.length());
			String[] arr = line.split(",");
			int arrlen = arr.length;
//			pt("arrlen=" + arrlen);
			ret = new int[arrlen];
			for (int i=0; i<arrlen; i++) {
				// 循环添加元素
				ret[i] = Integer.valueOf(arr[i]);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		return ret;
	}

}

class SolutionV2 {

    public int shortestSubarray(int[] nums, int k) {
    	int numslen = nums.length;
    	long[] P = new long[numslen + 1];
    	for (int i=0; i<numslen; i++) {
    		P[i+1] = P[i] + nums[i];
    	}
    	
    	int result = nums.length + 1;
    	
//    	pt(Arrays.toString(P));
    	
    	Deque<Integer> qi = new LinkedList<Integer>();
//    	int numslenadd1 = numslen + 1;
//    	for (int i=0; i<numslenadd1; i++) {
//    		qi.add(i);
//    	}
//    	pt("qi=" + qi);
    	
    	pt(Arrays.toString(P));
    	for (int y=0; y<P.length; y++) {
    		// Want opt(y) = largest x with P[x] <= P[y] - K;
    		pt("y=" + y);
    		while (!qi.isEmpty() && P[y] <= P[qi.getLast()]) {
    			int rret = qi.removeLast();
    			pt("1 rret=" + rret);
    		}
    		while (!qi.isEmpty() && P[y] >= (P[qi.getFirst()] + k)) {
    			int rfirst = qi.removeFirst();
    			result = Math.min(result, y - rfirst);
    			pt("2 rfirst=" + rfirst + ", result=" + result);
    		}
    		
    		qi.addLast(y);
    		pt(qi);
    	}
    	
//    	pt("2 result=" + result);
    	
    	return result < (numslen+1) ? result : -1;
    }
    
}